Network coding allows a node in a network to generate output data by mixing (or computing certain functions of) its received data. This extends the conventional routing scheme that only allows a node to forward its received data. The broadcast property of the wireless medium renders network coding particularly useful for wireless networks. For instance, a single broadcast transmission on a wireless network of a proper mixture packet may simultaneously present useful information to multiple wireless nodes.
By way of example, FIG. 1 illustrates the general concept of network coding in a wireless network 100. The network 100 includes wireless node A, wireless node R, and wireless node B, where node A and node B are both within the wireless communication range of node R. As can be seen from FIG. 1, node A has packet x1, node B has packet x2, and node R has packets x1 and x2. Assume that node A needs packet x2 and node B needs packet x1.
One technique of supplying x1 and x2 to node A and node B is called traditional piggybacking. Traditional piggybacking concatenates packets such that, for example, in FIG. 1, x1 and x2 are combined to obtain a mixture packet that is the size of x1 added to x2. The disadvantage of traditional piggybacking is that the size of the mixture packet increases rapidly as more packets are added. One recent approach called physical piggybacking represents an improvement over traditional piggybacking. Physical piggybacking combines, for example, two packets into one packet without increasing the size of the packet. This means that the size of the resultant mixture packet is no greater that the largest packet being added together. This is achieved in part by using XOR operations. Referring to FIG. 1, physical piggybacking means that a single transmission of a mixture packet x1+x2 (where ‘+’ stands for the bit-wise XOR of the two packets) by node R will simultaneously present x2 to node A and x1 to node B. Since node A already has x1 it can compute x2 by subtracting x1 from the received mixture packet x1+ x2. Similarly node B can compute packet x1. This is an example of a single transmission that fulfills two tasks.
In order to implement this in practice, node R needs to have some way of knowing that node A has x1 and node B has x2. A recent wireless network coding framework takes advantage of physical piggybacking to improve the efficiency of unicasting in multi-hop wireless networks. In this approach, each node snoops on the medium and buffers whatever packets that it hears. A node also informs its neighbors which packets they have overheard. This allows nodes to have some knowledge of what packets are available at each neighboring node. Based on this knowledge, each node then determines whether there are opportunities to do mixing. Using the example of FIG. 1, node A may have overheard x1 when some other node transmitted x1 to node R. Node A then can explicitly tell node R that it has x1, thereby allowing node R to detect the mixing opportunity. Thus, in the general sense, this type of network coding scheme is a data-driven framework consisting of two essential modules: data availability distribution and data distribution. The former enables a node to obtain an approximate view of the data each of its neighbors has (i.e., “who has what?”), which is used to guide the actual distribution of data.